package com.example.demo1.suanfa;

import com.example.demo1.service.OrderService;
import org.apache.log4j.RollingFileAppender;
import org.apache.tomcat.util.modeler.FeatureInfo;

import javax.swing.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author zx
 * @Date 2022/2/11 13:52
 * @Version 1.0
 */
public class TanXinSuanFa {
    int[] values = new int[] {1,2,5};

    public int findMinCom2(int amount){
        return dfs(amount , values.length -1);
    }

    public int dfs(int amount,int i){
        if (amount == 0){
            return 0;
        }
        int use = amount/values[i];
        return use+dfs(amount-use*values[i],i-1);
    }


    /**
     * 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
     *
     * 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
     *
     * 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
     *
     * 注意，一开始你手头没有任何零钱。
     *
     * 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
     *
     * 示例 1：
     * 输入：[5,5,5,10,20]
     * 输出：true
     * 解释：
     * 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
     * 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
     * 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
     * 由于所有客户都得到了正确的找零，所以我们输出 true。
     *
     * 示例 2：
     * 输入：[5,5,10]
     * 输出：true
     *
     * 示例 3：
     * 输入：[10,10]
     * 输出：false
     *
     * 示例 4：
     * 输入：[5,5,10,10,20]
     * 输出：false
     * 解释：
     * 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
     * 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
     * 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
     * 由于不是每位顾客都得到了正确的找零，所以答案是 false。
     *
     * 思路：当给别人进行找零时，尽量先用大面额的找个他，比如20找15时，先用10元，再用5元。当所拥有的钱数无法满足找零时返回false。
     *
     * 0 <= bills.length <= 10000
     * bills[i] 不是 5 就是 10 或是 20
     */
    public boolean lemonadeChange(int[] bills){
        int fives = 0,tens = 0 ;
        for (int bill : bills) {
            if (bill == 5){
                fives++;
            } else if (bill == 10){
                if (fives > 0){
                    fives--;
                    tens++;
                } else {
                    return false;
                }
            } else {//拿20过来
                int t = 15;
                if (tens > 0){
                    t -= 10;
                    tens--;
                }
                while (t > 0 && fives > 0 ){
                    t -= 5;
                    fives--;
                }
                if (t > 0){
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
     *
     * 注意：
     *
     * 你可以假设胃口值为正。
     * 一个小朋友最多只能拥有一块饼干。
     *
     * 示例 1:
     * 输入: [1,2,3], [1,1]
     * 输出: 1
     * 解释:
     * 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
     * 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
     * 所以你应该输出1。
     *
     * 示例 2:
     * 输入: [1,2], [1,2,3]
     * 输出: 2
     */
//    public int minimumSum(int num){
//        int[] a = new int[4];
//        for (int i = 0;i<4;i++){
//            a[i] = num%10;
//        }
//
//    }


    /**
     * 7.移掉k位数字 LeetCode402
     * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
     *
     * 注意:
     *
     * num 的长度小于 10002 且 ≥ k。
     * num 不会包含任何前导零。
     * 示例 1 :
     *
     * 输入: num = “1432219”, k = 3
     * 输出: “1219”
     * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
     * 示例 2 :
     *
     * 输入: num = “10200”, k = 1
     * 输出: “200”
     * 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
     * 示例 3 :
     *
     * 输入: num = “10”, k = 2
     * 输出: “0”
     * 解释: 从原数字移除所有的数字，剩余为空就是0。
     *
     * 思路：先让正序
     */
    public String removeKdigits(String num, int k) {
        //用一个链表模拟栈
        LinkedList<Character> stack = new LinkedList<Character>();

        for(char c : num.toCharArray()) {
            while(stack.size() > 0 && k > 0 && stack.peekLast() >c) {
                stack.removeLast();
                k--;
            }
            stack.add(c);
        }

        //当K还没用完，序列已经变为顺序了，那么从栈后面直接删除即可
        while(k-- > 0){
            stack.removeLast();
        }

        //将这个栈（链表）转换为最终的string，另外若前面是0，注意删除
        StringBuilder res = new StringBuilder();
        boolean prezero = true;
        for(char c : stack) {
            if(prezero && c == '0') continue;
            prezero = false;
            res.append(c);
        }

        if(res.length() == 0) return "0";
        return res.toString();
    }


    /**
     * 9.分糖果 LeetCode135
     * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
     *
     * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
     *
     * 每个孩子至少分配到 1 个糖果。
     * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
     * 那么这样下来，老师至少需要准备多少颗糖果呢？
     *
     * 示例 1:
     *
     * 输入: [1,0,2]
     * 输出: 5
     * 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
     * 示例 2:
     *
     * 输入: [1,2,2]
     * 输出: 4
     * 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     * 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
     *
     * 思路：两个数组left和right，先后从左和从右遍历。
     *
     * 从左向右遍历left[]时，若left[i] > left[i-1] ，则left[i] = left[i-1] +1
     * 从右向左遍历right[]时，若right[i] > right[i+1] ，则right[i] = righr[i+!] +1
     * 最终，计算数量res 取left[i]和right[i]中较大的那个
     */
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        Arrays.fill(left,1);
        //从左遍历
        for (int i=1;i<ratings.length;i++){
            if (ratings[i]>ratings[i-1])
                left[i] = left[i-1]+1;
        }

        int res = left[ratings.length -1];
        int[] right = new int[ratings.length];
        Arrays.fill(right, 1);
        for(int i = ratings.length - 2 ; i >=0 ;i --) {
            if(ratings[i+1] < ratings[i])
                right[i] = right[i +1] +1;
            res += Math.max(left[i] ,right[i] );
        }
        return res;

    }

    /**
     * 9.去除重复字母 LeetCode316
     * 给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     *
     * 示例 1:
     *
     * 输入: “bcabc”
     * 输出: “abc”
     * 示例 2:
     *
     * 输入: “cbacdcbc”
     * 输出: “acdb”
     *
     * 思路：
     *
     * 遍历字符串里的字符，如果读到的字符的 ASCII 值是升序，依次存到一个栈中；
     * 如果读到的字符在栈中已经存在，这个字符我们不需要；（这里用一个flag[] 来存放每个元素是否已经在栈中）
     * 如果读到的 ASCII 值比栈顶元素严格小，看看栈顶元素在后面是否还会出现，如果还会出现，则舍弃栈顶元素，而选择后出现的那个字符，这样得到的字典序更小。
     * !stack.empty()
     * ASCII 值比栈顶元素严格小： curChar < stack.peek()
     * 当前位置不是最后出现的位置， charLastIndex[stack.peek() - 'a'] >= i （这里charLastIndex数组保存每个元素在string中最后出现的位置）
     * 最后的结果即为stack中的。
     */


    public static void main(String[] args) {
        int[] arrays = {1,2,3,4,5};
        Arrays.fill(arrays,1);
        for (int array : arrays) {
            System.out.println(array);
        }


        TanXinSuanFa tanXinSuanFa = new TanXinSuanFa();
        int minCom2 = tanXinSuanFa.findMinCom2(13);
        System.out.println(minCom2);

        System.out.println("-------------------");

        int[] bills = {5,5,10,10,20};
        boolean b = tanXinSuanFa.lemonadeChange(bills);
        System.out.println(b);

        System.out.println("-------------------");

        //7.
        System.out.println(tanXinSuanFa.removeKdigits("100219", 2));

        System.out.println("-------------------");

        //9.
        int[] ints = {1,0,2};
        int candy = tanXinSuanFa.candy(ints);
    }
}
